﻿#define _CRT_SECURE_NO_WARNINGS 1
#pragma warning(disable:4996)
#include<stdio.h>
//给定一个大小为 n 的数组 nums ，返回其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n / 2 ⌋ 的元素。
//你可以假设数组是非空的，并且给定的数组总是存在多数元素。
int majorityElement(int* nums, int numsSize) {
    int winner = nums[0];   //刚来的士兵占据高地
    int cnt = 1;            //阵营人数+1
    int i = 0;
    for (i = 1; i < numsSize; i++) {
        if (nums[i] == winner) {  //若相同元素
            cnt++; //同阵营加1
        }
        else if (cnt == 0) {     //无人占据高地
            winner = nums[i];
            cnt++;
        }
        else  cnt--;             //不同元素相互消杀
    }
    return winner;
}
int main(){
    int arr[] = { -1,-1,-1,1,2,1 };
    int sz = sizeof(arr) / sizeof(arr[0]);
    printf("%d", majorityElement(arr, sz));
    return 0;
}